什麼是 RSA？

RSA（Rivest–Shamir–Adleman）是一種廣泛使用的非對稱加密演算法，過程中會使用到一對金鑰——公開金鑰（Public Key）和私密金鑰（Private Key）。RSA 使用公開金鑰來加密資料，確保透過互聯網進行資料共享時，不會被未經授權的人取得，維持安全性。公開金鑰的破解難度極高，RSA 具有高度的抗破解能力，能有效抵禦攻擊。

從上圖可以發現公開金鑰用來加密資料，任何人都可以使用接收者的公開金鑰來加密資料，而只有擁有對應私密金鑰的接收者才能解密資料，確保資料的安全性與機密性。

RSA 的基本原理

RSA 的安全性來自於大數分解的困難性，也就是將一個大合數分解為質因數的難度。以下是 RSA 的主要步驟：

1. 產生一對金鑰

• 選擇兩個大質數：選兩個非常大的質數，也就是這兩個數字只有 1 和它們自己能被整除（例如 101 和 113，但實際上我們要找的數字比這組數字大很多）。
• 計算它們的乘積：把這兩個數字相乘，得到一個新數字 n 。
• 計算歐拉函數：這步驟是為了後面的加密和解密做準備，計算出 (p-1) × (q-1)。
• 選擇公開指數 e：通常選擇 65537，確保它和之前計算的數互質。
• 計算私密指數 d：用來解密的數字，它滿足 d × e 除以歐拉函數後餘數為 1。

以上步驟完成後就可以得到：

• 公開金鑰：包含 n 和 e ，可以公開分享。
• 私密金鑰：包含 n 和 d ，要保密不能洩漏。

2. 加密資料

當我們想要發送秘密訊息給其他人時：

• 將訊息轉換成數字：例如，把「HELLO」轉換成一個數字 m。
• 使用公開金鑰加密：計算 c = (m^e) mod n ，這裡的 c 就是加密後的密文。

任何人都有你的公開金鑰，都可以把訊息加密後發送給你，但只有你能解密。

3. 解密資料

當收到加密的訊息時，使用私密金鑰來解密：

• 使用私密金鑰解密：計算 m = (c^d) mod n，這樣就能得到原本的訊息數字 m。
• 將數字轉回原文：把數字 m 轉回「HELLO」的文字。

RSA 的安全性

足夠大的質數分解，複雜性越高，加密通信的安全性也會跟著提升，因此破解會變得更加困難，而且只有擁有私密金鑰的人才能解密信息，因此 RSA 的安全性很高。

RSA 的應用

1. 可以使用在安全通信，像是HTTPS中的數據加密和身份驗證。
2. 運用在數位簽章，驗證訊息的來源和完整性。
3. 加密電子郵件確保內容能夠被保護。
4. 虛擬私人網路（VPN）能夠保護數據傳輸的安全。

圖片來源:
https://library.mosse-institute.com/articles/2022/06/introduction-to-rsa-encryption/introduction-to-rsa-encryption.html